#include <stdio.h>
#include "tree_basic.h"
#include <queue>
using namespace std;

#define NUMELEMENT 10

// create a new node with a specific value
TREENODE* newTreeNode(int data) {
	TREENODE* node = new TREENODE;
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

// Insert a node in the binary search tree (BST)
TREENODE* insertBST(TREENODE* root, int data) {
	if (root == NULL) {
		root = newTreeNode(data);
	}
	else {
		if (data <= root->data) {
			root->left = insertBST(root->left, data);
		} 
		else {
			root->right = insertBST(root->right, data);
		}
	}
    return root; 
}

// Pre-order traversal is a kind of depth-first traversal 
// It visits in this order: root -> traverse left subtree -> traverse right subtree
void traversal_preorder(TREENODE* root) {
	if (root != NULL) {
		printf("%d ", root->data);
		traversal_preorder(root->left);
		traversal_preorder(root->right);
	}
}

// In-order traversal is a kind of depth-first traversal 
// It visits in this order: traverse left subtree -> root -> traverse right subtree
void traversal_inorder(TREENODE* root) {
	if (root != NULL) {		
		traversal_inorder(root->left);
		printf("%d ", root->data);
		traversal_inorder(root->right);
	}
}

// Post-order traversal is a kind of depth-first traversal 
// It visits in this order: traverse left subtree -> traverse right subtree -> root
void traversal_postorder(TREENODE* root) {
	if (root != NULL) {		
		traversal_postorder(root->left);
		traversal_postorder(root->right);
		printf("%d ", root->data);
	}
}

// Breadth-first traversal
// It visits the nodes in level-order.
void traversal_breadthFirst(TREENODE* root) {
	// bread-first traversal requires a queue to store the nodes.
	queue<TREENODE*> myqueue;
	TREENODE* tmp;
	if (root == NULL)
		return;
	myqueue.push(root);
	while(myqueue.size() > 0) {		
		tmp = myqueue.front();
		myqueue.pop();
		printf("%d ", tmp->data);
		if (tmp->left != NULL) {
			myqueue.push(tmp->left);
		}
		if (tmp->right != NULL) {
			myqueue.push(tmp->right);
		}
	}	
}

bool isBST_helper(TREENODE* node, int min, int max) {
	if (node == NULL)
		return true;
	// if this node vilolates the BST property, return false
	if (node->data < min || node->data > max)
		return false;
	// otherwise check whether both the left subtree and the right subtree follow BST rule
	return isBST_helper(node->left, min, node->data) && isBST_helper(node->right, node->data+1,max);
}

bool isBST(TREENODE* node) {
	return isBST_helper(node, -99999999, 99999999);
}


void printArray(int path[], int length) {
	for (int i = 0; i < length; i++)
		printf("%d ", path[i]);
	printf("\n");
}

void printPathHelper(TREENODE* node, int path[], int length) {
	if (node == NULL) 
		return;

	path[length] = node->data;
	length++;

	if (node->left == NULL && node->right == NULL)
		printArray(path, length);
	else {
		printPathHelper(node->left, path, length);
		printPathHelper(node->right, path, length);
	}	
}

void printPaths(TREENODE* node) {
	int path[1000];

	printPathHelper(node, path, 0);
}

void test_tree_basic() {
	TREENODE* root = NULL;
	int data[NUMELEMENT] = {3, 4, 1, 8, 6, 10, 0, 7, 12, 1};

	printf("Start with the empty binary search tree (BST)\n");    
	for (int i = 0; i < NUMELEMENT; i++ ) {
		printf("Insert %d in the BST\n", data[i]);
		root = insertBST(root, data[i]);
	}
	printf("\n");

	printf("Pre-order traversal: \n");
	traversal_preorder(root);
	printf("\n");

    printf("In-order traversal: \n");
	traversal_inorder(root);
	printf("\n");

	printf("Post-order traversal: \n");
	traversal_postorder(root);
	printf("\n");

	printf("Breadth-first traversal: \n");
	traversal_breadthFirst(root);
	printf("\n");
	
	printf("Display all paths in this tree: \n");
	printPaths(root);
	printf("\n");


	if (isBST(root))
		printf ("This tree is a BST.\n");
	else
		printf ("NOT a BST.\n");

	TREENODE* newroot = newTreeNode(50);
	newroot->right = root;
	printf("In-order traversal: \n");
	traversal_inorder(newroot);
	printf("\n");

	printf("Breadth-first traversal: \n");
	traversal_breadthFirst(newroot);
	printf("\n");

	if (isBST(newroot))
		printf ("This tree is a BST.\n");
	else
		printf ("NOT a BST.\n");
		

}
